package org.basic.algorithm.medium;

import org.basic.common.entity.ListNode;

/**
 * 反转链表II
 * <p>
 * 给你单链表的头指针 head 和两个整数 left 和 right，其中 left <= right。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。
 * <p>
 * 示例 1：
 * 输入：head = [1,2,3,4,5], left = 2, right = 4
 * 输出：[1,4,3,2,5]
 * <p>
 * 示例 2：
 * 输入：head = [5], left = 1, right = 1
 * 输出：[5]
 * <p>
 * 提示：
 * 链表中节点数目为 n
 * 1 <= n <= 500
 * -500 <= Node.val <= 500
 * 1 <= left <= right <= n
 *
 * @author LiKun
 * @date 2021/10/23 14:06
 */
public class ReverseLinkedListII {
    public static void main(String[] args) {
        ListNode listNode = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, null))));
        System.out.println(reverseList(listNode, 1, 4));
    }

    public static ListNode reverseList(ListNode head, int left, int right) {
        if (left != right) {
            ListNode reverseHead, leftNodeTail, middleNodeHead, middleNodeTail, rightNodeHead;

            leftNodeTail = randomAccess(head, left);
            middleNodeTail = randomAccess(head, right + 1);
            middleNodeHead = (leftNodeTail == null) ? head : leftNodeTail.next;

            rightNodeHead = middleNodeTail.next;
            middleNodeTail.next = null;

            if (leftNodeTail == null) {
                head = reverseNode(middleNodeHead, rightNodeHead);
            } else {
                leftNodeTail.next = null;
                leftNodeTail.next = reverseNode(middleNodeHead, rightNodeHead);
            }
        }

        return head;
    }

    /**
     * 截取给定的 intercept 链表的头部并拼接到 splice 链表的尾部 ---> 循环执行，直到 intercept == null
     *
     * @param head   被截取的链表的头部节点
     * @param splice 被拼接的链表的头部节点
     */
    private static ListNode reverseNode(ListNode intercept, ListNode splice) {
        ListNode pointer;
        while ((pointer = intercept) != null) {
            intercept = intercept.next;
            pointer.next = splice;
            splice = pointer;
        }
        return splice;
    }

    /**
     * 获取给定首位置的 ListNode 的父节点
     *
     * @param listNode 链表头节点
     * @param index    索引(从 1 开始)
     *
     * @return 给定位置的节点
     */
    private static ListNode randomAccess(ListNode listNode, int index) {
        ListNode result = null;
        while (--index > 0) {
            if (listNode == null) {
                break;
            }
            result = listNode;
            listNode = listNode.next;
        }
        return result;
    }
}
